翻訳と辞書 Words near each other ・ Lensko ・ Lensky ・ Lensky (rural locality) ・ Lensky District ・ Lensky District, Arkhangelsk Oblast ・ Lensky District, Sakha Republic ・ Lensless glasses ・ Lenslet ・ Lenslok ・ Lensman (disambiguation) ・ Lensman (game) ・ Lensman series ・ Lensmann ・ Lensmeter ・ Lenstra ・ Lenstra elliptic curve factorization ・ Lenstra–Lenstra–Lovász lattice basis reduction algorithm ・ Lensvik ・ Lensvik Church ・ Lenswood ・ Lenswood wine sub-region ・ Lenswood, South Australia ・ Lensworld.eu-Zannata ・ Lensy Debboudt ・ Lent ・ Lent (album) ・ Lent (disambiguation) ・ Lent Bumps ・ Lent Bumps 1998 ・ Lent Bumps 1999 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Lenstra elliptic curve factorization ： ウィキペディア英語版 Lenstra elliptic curve factorization The Lenstra elliptic curve factorization or the elliptic curve factorization method (ECM) is a fast, sub-exponential running time algorithm for integer factorization which employs elliptic curves. For general purpose factoring, ECM is the third-fastest known factoring method. The second fastest is the multiple polynomial quadratic sieve and the fastest is the general number field sieve. The Lenstra elliptic curve factorization is named after Hendrik Lenstra. Practically speaking, ECM is considered a special purpose factoring algorithm as it is most suitable for finding small factors. , it is still the best algorithm for divisors not greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time is dominated by the size of the smallest factor ''p'' rather than by the size of the number ''n'' to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general purpose techniques. The largest factor found using ECM so far has 83 digits and was discovered on 7 September 2013 by R. Propper.〔(50 largest factors found by ECM )〕 Increasing the number of curves tested improves the chances of finding a factor, but they are not linear with the increase in the number of digits. ==Lenstra's elliptic curve factorization== The Lenstra elliptic curve factorization method to find a factor of the given natural number $n$ works as follows: # Pick a random elliptic curve over $\backslash mathbb/n\backslash mathbb$, with equation of the form $y^2\; =\; x^3\; +\; ax\; +\; b\backslash pmod\; n$ together with a non-trivial point $P(x\_0,y\_0)$ on it. #:This can be done by first picking random $x\_0,y\_0,a\backslash in\backslash mathbb/n\backslash mathbb$, and then calculating $b\; =\; y\_0^2\; -\; x\_0^3\; -\; ax\_0\backslash pmod\; n$. #: # 'Addition' of ''P'' and ''Q'' as points in general defines a group operation ''P'' ⊕ ''Q'' on the curve whose product can be computed from formulas given in the article on elliptic curves. #:Using this assumption, we can form repeated multiples of a point ''P'': ''kP'' = ''P'' ⊕ ... ⊕ ''P'' (''k'' times). The addition formulas involve the taking the modular slope of a chord joining ''P'' and ''Q'', and thus division between residue classes modulo ''n'', performed using the extended Euclidean algorithm. In particular, division by some ''v'' (mod ''n'') includes calculation of the greatest common divisor gcd(''v'', ''n''). #: If the slope is of the form ''u''/''v'' with gcd(''u'', ''n'') = 1, then ''v'' = 0 (mod ''n'') means that the result of the ⊕-addition will be $\backslash infty$, the point 'at infinity' corresponding to the intersection of the 'vertical' line joining ''P'' (''x'', ''y''), ''P (''x'', −''y'') and the curve. However, if gcd(''v'', ''n'') is neither 1 nor ''n'', then the ⊕-addition will not produce a meaningful point on the curve, which shows that our elliptic curve is not a group (mod ''n''), but, more importantly for now, gcd(''v'', ''n'') is a non-trivial factor of ''n''. #: # Compute ''eP'' on the elliptic curve (mod ''n''), where ''e'' is product of many small numbers: say, a product of small primes raised to small powers, as in the ''p'' − 1 algorithm, or the factorial ''B''! for some not too large ''B''. This can be done efficiently, one small factor at a time. Say, to get ''B''!''P'', first compute 2''P'', then 3(2''P''), then 4(3!''P''), and so on. Of course, ''B'' should be small enough so that ''B''-wise ⊕-addition can be performed in reasonable time. #: # # *If we were able to finish all the calculations above without encountering non-invertible elements (mod ''n''), then we need to try again with some other curve and starting point. # *If at some stage we found ''kP'' = ∞ (''infinity'' on the elliptic curve), we should start over with a new curve and starting point, since this point $\backslash infty$ is the group identity element, so is unchanged under any further addition operations. # *If we encountered a gcd(''v'', ''n'') at some stage that was neither 1 nor ''n'', then we are done: it is a non-trivial factor of ''n''. The time complexity depends on the size of the factor and can be represented by exp((√2 + o(1)) √(ln ''p'' ln ln ''p'')), where ''p'' is the smallest factor of ''n'', or $L\_p\backslash left()$, in L-notation. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lenstra elliptic curve factorization」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.